class Solution {
public:
    long long rootSum(TreeNode* root, long long targetSum) {
        if (!root) {
            return 0;
        }

        long long ret = 0;
        if (root->val == targetSum) {
            ret++;
        }

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }

    long long pathSum(TreeNode* root, long long targetSum) {
        if (!root) {
            return 0;
        }

        long long ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
};

